www.gusucode.com > VC 2D游戏编辑器-源码程序 > VC 2D游戏编辑器-源码程序/code/game_Source/GameLib/findpath.cpp

    //Download by http://www.NewXing.com
#include "findpath.h"
#include "define.h"
#include "globle.h"
#include "globle_func.h"
#include "..\\newgame.h"

FINDPATH8::FINDPATH8( )
{
	Dir = NULL;
	Dir1 = NULL;
	bBeginDir = false;
	IsFind = false;
	IsTooFar = false;
	Table = new bool[TABLE_X*TABLE_Y];
	MaxAct=8;				//移动方向总数
	Level=-1;				//第几步
	LevelComplete=0;		//这一步的搜索是否完成
	AllComplete=0;			//全部搜索是否完成
	cur_x=1;
	cur_y=1;				//现在的x和y坐标
	TargetX=0;
	TargetY=0;				//目标x和y坐标
	BaseX=0;
	BaseY=0;				//开始x和y坐标
}

FINDPATH8::~FINDPATH8( )
{
	PA_SAFE_DELETE(Table);
}

void FINDPATH8::find(long lStartX, long lStartY, long lEndX, long lEndY)
{
	if(Dir)
	{
		while(Dir)
		{
			pLink1 = Dir;
			Dir = Dir->Next;
			delete [] pLink1;
		}
		Dir = NULL;
	}
	cur_x = BaseX = lStartX/32;
	cur_y = BaseY = lStartY/32;
	TargetX = iTX = lEndX/32;
	TargetY = iTY = lEndY/32;
	if((TargetX == cur_x)&&(TargetY == cur_y))
	{
		IsFind = true;
		return;
	}
	int nx, ny;
	do
	{
		nx = abs(iTX - BaseX);
		ny = abs(iTY - BaseY);
		if(nx > 32)
			if(iTY > BaseX)
				TargetX = BaseX + 32;
			else
				TargetX = BaseX - 32;
		if(ny > 32)
			if(iTY > BaseY)
				TargetY = BaseY + 32;
			else
				TargetY = BaseY - 32;
		FindWay( );
		if(!IsFind)
		{
			FindNear( );
			if(Dir1)
			{
				while(Dir1)
				{
					pLink1 = Dir1;
					Dir1 = Dir1->Next;
					delete [] pLink1;
				}
				Dir1 = NULL;
			}
			cur_x = BaseX;
			cur_y = BaseY;
			FindWay( );
		}
		if(Dir == NULL)
		{
			Dir = Dir1;
			Dir1 = NULL;
		}
		else
		{
			pLink1->Next = Dir1;
			Dir1 = NULL;
		}
		BaseX = TargetX;
		BaseY = TargetY;
	}while((nx > 32)||(ny > 32));
		
	iTX = TargetX;
	iTY = TargetY;
	pLink1 = NULL;
}

void FINDPATH8::FindWay( )
{
	Level=-1; //第几步
	LevelComplete=0; //这一步的搜索是否完成
	AllComplete=0; //全部搜索是否完成
	IsFind = false;
	IsTooFar = false;

	if((BaseX == TargetX)&&(BaseY == TargetY))
	{
		IsFind = true;
		return;
	}

	iTableStartX = (BaseX+TargetX-TABLE_X)>>1;
	iTableStartY = (BaseY+TargetY-TABLE_Y)>>1;

	_pDir* pLink;
	memset(Table,0,TABLE_X*TABLE_Y*sizeof(bool));
	Table[(cur_y-iTableStartY)*TABLE_X+cur_x-iTableStartX]=true; //做已到过标记
	while (!AllComplete) //是否全部搜索完
	{
		Level++;LevelComplete=0; //搜索下一步
		if(Level > 1000)//搜索步数过多
		{
			LevelComplete=AllComplete=1; //退出
			IsTooFar = true;
		}
		pLink = new _pDir;
		pLink->dir = 0;
		pLink->Next = NULL;
		if(Dir1 == NULL)
		{
			pLink->Back = NULL;
			Dir1 = pLink;
			pLink1 = pLink;
			pLink = NULL;
		}
		else
		{
			pLink->Back = pLink1;
			pLink1->Next = pLink;
			pLink1 = pLink;
			pLink = NULL;
		}
		while (!LevelComplete)
		{
			pLink1->dir=GetNextAct( ); //改变移动方向
			if (pLink1->dir>MaxAct)
			{
				Back( );
				if (Level<0) //全部搜索完仍无结果
					LevelComplete=AllComplete=1; //退出
			}
			else if (ActOK( )) //移动方向是否合理
			{
				Test( ); //测试是否已到目标
				LevelComplete=1; //该步搜索完成
			}
		}
	}
}

void FINDPATH8::Test( )
{
	if ((cur_x==TargetX)&&(cur_y==TargetY)) //已到目标
	{
		IsFind = true;
		LevelComplete=AllComplete=1; //完成搜索
	}
}

int FINDPATH8::ActOK( )
{
	int tx=cur_x+dir8_x[pLink1->dir-1]; //将到点的x坐标
	int ty=cur_y+dir8_y[pLink1->dir-1]; //将到点的y坐标
	if (pLink1->dir>MaxAct) //方向错误？
		return 0;
	if ((tx>=Map->pHeader.nWidth)||(tx<0)||(tx < iTableStartX)||(tx >= iTableStartX+TABLE_X)) //x坐标出界？
		return 0;
	if ((ty>=Map->pHeader.nHeight)||(ty<0)||(ty < iTableStartY)||(ty >= iTableStartY+TABLE_Y)) //y坐标出界？
		return 0;
	if (Table[(ty-iTableStartY)*TABLE_X+tx-iTableStartX]) //已到过？
		return 0;
	if (Map->pSurfaceData[ty*Map->pHeader.nWidth+tx].nPass == 0) //有障碍？
		return 0;
	cur_x=tx;
	cur_y=ty; //移动
	Table[(ty-iTableStartY)*TABLE_X+tx-iTableStartX]=true; //做已到过标记
	return 1;
}

void FINDPATH8::Back( )
{
	Level--; //回上一层
	if(Level < 0)
	{
		delete Dir1;
		Dir1 = NULL;
		return;
	}
	cur_x -=dir8_x[pLink1->Back->dir-1];
	cur_y -=dir8_y[pLink1->Back->dir-1]; //退回原来的点
	pLink1 = pLink1->Back;
	delete[] pLink1->Next; //清除方向
	pLink1->Next = NULL;
}

int FINDPATH8::GetNextAct( ) //找到下一个移动方向。
//仔细看!
{
	float dis[8];
	int order[8];
	float t=2000;
	int i, j;
	if(Level > 0)
	{
		for (i = 0; i < 8; i++)
		{
			dis[i]=(dSqrt[dSquare[abs(cur_x+dir8_x[i]-TargetX)]+dSquare[abs(cur_y+dir8_y[i]-TargetY)]])*2+abs(dir8_y[i]-dir8_y[pLink1->Back->dir-1])+abs(dir8_x[i]-dir8_x[pLink1->Back->dir-1])+(abs(dir8_y[i]-dir8_y[pLink1->Back->dir-1])/2+abs(dir8_x[i]-dir8_x[pLink1->Back->dir-1])/2)*2;
		}
	}
	else
	{
		for (i = 0; i < 8; i++)
		{
			dis[i]=dSqrt[dSquare[abs(cur_x+dir8_x[i]-TargetX)]+dSquare[abs(cur_y+dir8_y[i]-TargetY)]];
		}
	}
	for (i = 0;i<8;i++)
		if (dis[i]<t)
		{
			order[0]=i+1;
			t=dis[i];
		}
	if (pLink1->dir==0)
		return order[0];
	dis[order[0]-1] = 32767;
	for(i = 1; i < 8; i++)
	{
		t = 32767;
		for(j = 0; j < 8; j++)
		{
			if(dis[j] < t)
			{
				order[i] = j + 1;
				t = dis[j];
			}
		}
		dis[order[i]-1] = 32767;
	}

	if (pLink1->dir==order[0])
		return order[1];
	if (pLink1->dir==order[1])
		return order[2];
	if (pLink1->dir==order[2])
		return order[3];
	if (pLink1->dir==order[3])
		return order[4];
	if (pLink1->dir==order[4])
		return order[5];
	if (pLink1->dir==order[5])
		return order[6];
	if (pLink1->dir==order[6])
		return order[7];
	if (pLink1->dir==order[7])
		return 9;
	return 9;
}

void FINDPATH8::FindNear( )
{
		long lStartX, lStartY, lNearX, lNearY, lR;
		int i;
		lStartX = TargetX;
		lStartY = TargetY;
		lR = 0;
		bool IsFindNear = false;
		while(!IsFindNear)
		{
			lR ++;			
			for(i = 0; i < 360; i +=1)
			{
				lNearX = (long)(lR*cos_O[i]) + lStartX;
				lNearY = (long)(lR*sin_O[i]) + lStartY;
				if(lNearX < 0)
					lNearX = 0;
				if(lNearY < 0)
					lNearY = 0;
				if(lNearX > Map->pHeader.nWidth-1)
					lNearX = Map->pHeader.nWidth-1;
				if(lNearY > Map->pHeader.nHeight-1)
					lNearY = Map->pHeader.nHeight-1;
				if(Table[(lNearY-iTableStartY)*TABLE_X+lNearX-iTableStartX])
				{
					IsFindNear = true;
					break;
				}
			}
		}
		TargetX = lNearX;
		TargetY = lNearY;
}

/*****************************************************************************/

FINDPATH4::FINDPATH4( )
{
	Dir = NULL;
	Dir1 = NULL;
	bBeginDir = false;
	IsFind = false;
	IsTooFar = false;
	Table = new bool[TABLE_X*TABLE_Y];
	MaxAct=4;				//移动方向总数
	Level=-1;				//第几步
	LevelComplete=0;		//这一步的搜索是否完成
	AllComplete=0;			//全部搜索是否完成
	cur_x=1;
	cur_y=1;				//现在的x和y坐标
	TargetX=0;
	TargetY=0;				//目标x和y坐标
	BaseX=0;
	BaseY=0;				//开始x和y坐标
}

FINDPATH4::~FINDPATH4( )
{
	PA_SAFE_DELETE(Table);
}

void FINDPATH4::find(long lStartX, long lStartY, long lEndX, long lEndY)
{
	if(Dir)
	{
		while(Dir)
		{
			pLink1 = Dir;
			Dir = Dir->Next;
			delete [] pLink1;
		}
		Dir = NULL;
	}
	cur_x = BaseX = lStartX/32;
	cur_y = BaseY = lStartY/32;
	TargetX = iTX = lEndX/32;
	TargetY = iTY = lEndY/32;
	if((TargetX == cur_x)&&(TargetY == cur_y))
	{
		IsFind = true;
		return;
	}
	int nx, ny;
	do
	{
		nx = abs(iTX - BaseX);
		ny = abs(iTY - BaseY);
		if(nx > 32)
			if(iTY > BaseX)
				TargetX = BaseX + 32;
			else
				TargetX = BaseX - 32;
		if(ny > 32)
			if(iTY > BaseY)
				TargetY = BaseY + 32;
			else
				TargetY = BaseY - 32;
		FindWay( );
		if(!IsFind)
		{
			FindNear( );
			if(Dir1)
			{
				while(Dir1)
				{
					pLink1 = Dir1;
					Dir1 = Dir1->Next;
					delete [] pLink1;
				}
				Dir1 = NULL;
			}
			cur_x = BaseX;
			cur_y = BaseY;
			FindWay( );
		}
		if(Dir == NULL)
		{
			Dir = Dir1;
			Dir1 = NULL;
		}
		else
		{
			pLink1->Next = Dir1;
			Dir1 = NULL;
		}
		BaseX = TargetX;
		BaseY = TargetY;
	}while((nx > 32)||(ny > 32));
		
	iTX = TargetX;
	iTY = TargetY;
	pLink1 = NULL;
}

void FINDPATH4::FindWay( )
{
	Level=-1; //第几步
	LevelComplete=0; //这一步的搜索是否完成
	AllComplete=0; //全部搜索是否完成
	IsFind = false;
	IsTooFar = false;

	if((BaseX == TargetX)&&(BaseY == TargetY))
	{
		IsFind = true;
		return;
	}

	iTableStartX = (BaseX+TargetX-TABLE_X)>>1;
	iTableStartY = (BaseY+TargetY-TABLE_Y)>>1;

	_pDir* pLink;
	memset(Table,0,TABLE_X*TABLE_Y*sizeof(bool));
	Table[(cur_y-iTableStartY)*TABLE_X+cur_x-iTableStartX]=true; //做已到过标记
	while (!AllComplete) //是否全部搜索完
	{
		Level++;LevelComplete=0; //搜索下一步
		if(Level > 1000)//搜索步数过多
		{
			LevelComplete=AllComplete=1; //退出
			IsTooFar = true;
		}
		pLink = new _pDir;
		pLink->dir = 0;
		pLink->Next = NULL;
		if(Dir1 == NULL)
		{
			pLink->Back = NULL;
			Dir1 = pLink;
			pLink1 = pLink;
			pLink = NULL;
		}
		else
		{
			pLink->Back = pLink1;
			pLink1->Next = pLink;
			pLink1 = pLink;
			pLink = NULL;
		}
		while (!LevelComplete)
		{
			pLink1->dir=GetNextAct( ); //改变移动方向
			if (pLink1->dir>MaxAct)
			{
				Back( );
				if (Level<0) //全部搜索完仍无结果
					LevelComplete=AllComplete=1; //退出
			}
			else if (ActOK( )) //移动方向是否合理
			{
				Test( ); //测试是否已到目标
				LevelComplete=1; //该步搜索完成
			}
		}
	}
}

void FINDPATH4::Test( )
{
	if ((cur_x==TargetX)&&(cur_y==TargetY)) //已到目标
	{
		IsFind = true;
		LevelComplete=AllComplete=1; //完成搜索
	}
}

int FINDPATH4::ActOK( )
{
	int tx=cur_x+dir4_x[pLink1->dir-1]; //将到点的x坐标
	int ty=cur_y+dir4_y[pLink1->dir-1]; //将到点的y坐标
	if (pLink1->dir>MaxAct) //方向错误？
		return 0;
	if ((tx>=Map->pHeader.nWidth)||(tx<0)||(tx < iTableStartX)||(tx >= iTableStartX+TABLE_X)) //x坐标出界？
		return 0;
	if ((ty>=Map->pHeader.nHeight)||(ty<0)||(ty < iTableStartY)||(ty >= iTableStartY+TABLE_Y)) //y坐标出界？
		return 0;
	if (Table[(ty-iTableStartY)*TABLE_X+tx-iTableStartX]) //已到过？
		return 0;
	if (Map->pSurfaceData[ty*Map->pHeader.nWidth+tx].nPass == 0) //有障碍？
		return 0;
	cur_x=tx;
	cur_y=ty; //移动
	Table[(ty-iTableStartY)*TABLE_X+tx-iTableStartX]=true; //做已到过标记
	return 1;
}

void FINDPATH4::Back( )
{
	Level--; //回上一层
	if(Level < 0)
	{
		delete Dir1;
		Dir1 = NULL;
		return;
	}
	cur_x -=dir4_x[pLink1->Back->dir-1];
	cur_y -=dir4_y[pLink1->Back->dir-1]; //退回原来的点
	pLink1 = pLink1->Back;
	delete[] pLink1->Next; //清除方向
	pLink1->Next = NULL;
}

int FINDPATH4::GetNextAct( ) //找到下一个移动方向。
//仔细看!
{
	int dis[4];
	int order[4];
	int t=2000;
	int i, j;
	if(Level > 0)
	{
		for (i = 0; i < 4; i++)
		{
			dis[i]=abs(cur_x+dir4_x[i]-TargetX) + abs(cur_y+dir4_y[i]-TargetY);
		}
	}
	else
	{
		for (i = 0; i < 4; i++)
		{
			dis[i]=abs(cur_x+dir4_x[i]-TargetX) + abs(cur_y+dir4_y[i]-TargetY);
			//dis[i]=dSqrt[dSquare[abs(cur_x+dir4_x[i]-TargetX)]+dSquare[abs(cur_y+dir4_y[i]-TargetY)]];
		}
	}
	for (i = 0;i<4;i++)
		if (dis[i]<t)
		{
			order[0]=i+1;
			t=dis[i];
		}
	if (pLink1->dir==0)
		return order[0];
	dis[order[0]-1] = 32767;
	for(i = 1; i < 4; i++)
	{
		t = 32767;
		for(j = 0; j < 4; j++)
		{
			if(dis[j] < t)
			{
				order[i] = j + 1;
				t = dis[j];
			}
		}
		dis[order[i]-1] = 32767;
	}

	if (pLink1->dir==order[0])
		return order[1];
	if (pLink1->dir==order[1])
		return order[2];
	if (pLink1->dir==order[2])
		return order[3];
	if (pLink1->dir==order[3])
		return 5;
	return 5;
}

void FINDPATH4::FindNear( )
{
		long lStartX, lStartY, lNearX, lNearY, lR;
		int i;
		lStartX = TargetX;
		lStartY = TargetY;
		lR = 0;
		bool IsFindNear = false;
		while(!IsFindNear)
		{
			lR ++;			
			for(i = 0; i < 360; i +=1)
			{
				lNearX = (long)(lR*cos_O[i]) + lStartX;
				lNearY = (long)(lR*sin_O[i]) + lStartY;
				if(lNearX < 0)
					lNearX = 0;
				if(lNearY < 0)
					lNearY = 0;
				if(lNearX > Map->pHeader.nWidth-1)
					lNearX = Map->pHeader.nWidth-1;
				if(lNearY > Map->pHeader.nHeight-1)
					lNearY = Map->pHeader.nHeight-1;
				if(Table[(lNearY-iTableStartY)*TABLE_X+lNearX-iTableStartX])
				{
					IsFindNear = true;
					break;
				}
			}
		}
		TargetX = lNearX;
		TargetY = lNearY;
}